package backMind

import "fmt"

// 地上有个m行n列的方格，一格机器人从坐标0，0开始移动，可以向左右上下移动一个格子
// 但不能进入行坐标和列坐标数位之和大于k的格子，例如当k=18 机器人能进入35，37 因为3+5+3+7=18
// 但不能进入35,38 因为3+5+3+8=19 请问该机器人能够达到多少格子

func RobotMove(k, rows, cols int) int {
	if rows <= 0 {
		return 0
	}
	if cols <= 0 {
		return 0
	}
	visited := map[string]bool{}

	var count = robotMove(k, rows, cols, 0, 0, visited)
	return count
}

func robotMove(k, rows, cols, row, col int, visited map[string]bool) int {
	var count = 0
	if check(k, rows, cols, row, col, visited) {
		visited[fmt.Sprintf("%v%v", row, col)] = true
		count = 1 +
			robotMove(k, rows, cols, row-1, col, visited) +
			robotMove(k, rows, cols, row, col-1, visited) +
			robotMove(k, rows, cols, row+1, col, visited) +
			robotMove(k, rows, cols, row, col+1, visited)
	}
	return count
}

// 检查当前坐标是否满足条件
func check(k, rows, cols, row, col int, visited map[string]bool) bool {
	if row >= 0 &&
		row < rows &&
		col >= 0 &&
		col < cols &&
		getDigitSum(row)+getDigitSum(col) <= k &&
		!visited[fmt.Sprintf("%v%v", row, col)] {
		return true
	}
	return false
}

// 求一个数的数位之和
func getDigitSum(num int) int {
	var sum = 0
	for num > 0 {
		sum += num % 10
		num /= 10
	}
	return sum
}
